package com.platform.modules.alg.alglib.poj3984;

import java.util.LinkedList;
import java.util.Queue;

public class Poj3984 {
    boolean mp[][] = new boolean[5][5];
    boolean vis[][] = new boolean[5][5];
    int dir[][] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public String output = "";

    private node pre[][] = new node[10][10];

    public Poj3984() {
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                pre[i][j] = new node();
            }
        }
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        for (int i = 0; i < 5; i++) {
            String[] words = line[i].split(" ");
            for (int j = 0; j < 5; j++) {
                mp[i][j] = words[j].equals("1");
            }
        }

        bfs();
        node ed = new node();
        ed.x = ed.y = 4;
        print(ed);

        return output;
    }

    void bfs() {
        Queue<node> que = new LinkedList<>(); // 创建一个普通队列(先进先出)
        node st = new node();
        st.x = 0;
        st.y = 0;
        que.add(st);
        vis[0][0] = true;
        while (!que.isEmpty()) {
            node now = que.peek();
            que.poll();
            if (now.x == 4 && now.y == 4)
                return;
            for (int i = 0; i < 4; i++) {
                node next = new node();
                next.x = now.x + dir[i][0];
                next.y = now.y + dir[i][1];
                if (next.x >= 0 && next.x < 5 && next.y >= 0 && next.y < 5 && !mp[next.x][next.y] && !vis[next.x][next.y]) {
                    vis[next.x][next.y] = true;
                    que.add(next);
                    pre[next.x][next.y] = now;
                }
            }
        }
    }

    void print(node cur) {
        if (cur.x == 0 && cur.y == 0) {
            output += "(0,0)\n";
            return;
        }
        print(pre[cur.x][cur.y]); // 逆序输出
        output += "(" + cur.x + "," + cur.y + ")\n";
    }
}

class node {
    int x;
    int y;
}
